package com.origin.niuke;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/4/13 14:57
 * 算法：堆
 */
public class 单源最短路 {
    public static void main(String[] args) {
        System.out.println(new 单源最短路().method());
    }

    public int findShortestPath(int n, int m, int[][] graph) {
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(dist[i], Integer.MAX_VALUE);
        for (int[] edge : graph)
            dist[edge[0] - 1][edge[1] - 1] = Math.min(edge[2], dist[edge[0] - 1][edge[1] - 1]);
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        queue.offer(new int[]{0, 0});
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            if (poll[0] == n - 1) return poll[1];
            for (int i = 0; i < n; i++) {
                if (dist[poll[0]][i] != Integer.MAX_VALUE)
                    queue.offer(new int[]{i, poll[1] + dist[poll[0]][i]});
            }
        }
        return -1;
    }

    public boolean method() {
        int[][] matrix = new int[][]{{1, 100}, {2, 50}, {3, 30}};
        int target = 291;
        int[] dp = new int[target + 1];
        Arrays.fill(dp, 0);
        for (int[] ints : matrix) {
            // v - 数值，w - 个数
            int v = ints[0], w = ints[1];
            for (int i = target; i >= 0; i--) {
                for (int j = 1; j <= w && j * v <= i; j++) dp[i] = Math.max(dp[i], dp[i - j * v] + j * v);
            }
        }
        List<Integer> list = new ArrayList<>();
        list.toArray(new Integer[0]);
        System.out.println(Arrays.toString(dp));
        return dp[target] == target;
    }

}
